package s7_查找算法.search3_斐波拉契查找算法;

import s6_排序算法.BaseSort;
import s6_排序算法.sort1_交换排序.QuickSort;
import s7_查找算法.BaseSearch;

import java.util.Arrays;

/**
 * <code>{@link FibonacciSearch}</code>
 * <p>
 * description: FibonacciSearch
 * <p>
 *
 * @author 西瓜瓜 on 2022/2/21 21:54
 * 斐波那契查找算法
 * 1.mid = low + f[k-1] -1;
 * 2.f[] 为斐波拉契数列
 * 3.arr[]初始化要扩容到f[k]的长度
 */
public class FibonacciSearch extends BaseSearch {

    public static void main(String[] args) {
        int[] arr = BaseSort.normal();
        System.out.println(Arrays.toString(arr));
        new QuickSort().asc(arr);
        System.out.println(Arrays.toString(arr));


        int target = 2;
        int search = new FibonacciSearch().search(arr, target);
        System.out.println(search);
    }

    public static int maxSize = 20;

    /**
     * 得到一个斐波那契数列
     * @return
     */
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for(int i=2; i<maxSize; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }

    @Override
    public int search(int[] arr, int target) {
        int low = 0, high = arr.length-1;
        // 表示斐波那契分割数值的下标
        int k=0;
        int mid=0;
        // 获取斐波拉契数列
        int[] f = fib();
        // 获取斐波那契分割数值的下标
        while(high > f[k] - 1) {
            k++;
        }
        // 因为f[k]值可能大于数组长度，因此需要使用Arrays类构造新的数组，并指向arr[]
        // 不足的部分会使用0填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        // 实际上需要使用a[high] 填充不足的部分
        for (int i=high+1; i<temp.length; i++) {
            temp[i] = arr[high];
        }

        // 使用while来循环处理，找到target
        while(low <= high) {
            mid = low + f[k-1] -1;
            if(target < temp[mid]) {
                high = mid - 1;
                k--;
            } else if(target > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                // 需要确定返回的是哪个下标
                if(mid <= high) {
                    return mid;
                }
                return high;
            }
        }

        return -1;
    }
}
